package cn.corffen.test.algorithm.leetcode;

import java.util.*;

public class Solution {

    public static void main(String[] args) {

        int[] nums = new int[]{1, 2, 2, 2, 3, 4, 9, 20};
//        int val1 = 2;
//        int val2 = 5;
//        int valPosition1 = getPosition(nums, val1);
//        int valPosition2 = getPosition(nums, val2);
//        System.out.println(String.format(Locale.CHINA, "valPosition1=%d,valPosition2=%d", valPosition1, valPosition2));

        int dumplicate = 2;
        int[] result = deleteDumplicate1(nums, dumplicate);
        System.out.println(String.format(Locale.CHINA, "after nums=%s,after size=%d", Arrays.toString(result), result.length));
    }

    public int crossSum(int[] nums, int left, int right, int p) {
        if (left == right) return nums[left];

        int leftSubsum = Integer.MIN_VALUE;
        int currSum = 0;
        for (int i = p; i > left - 1; --i) {
            currSum += nums[i];
            leftSubsum = Math.max(leftSubsum, currSum);
        }

        int rightSubsum = Integer.MIN_VALUE;
        currSum = 0;
        for (int i = p + 1; i < right + 1; ++i) {
            currSum += nums[i];
            rightSubsum = Math.max(rightSubsum, currSum);
        }

        return leftSubsum + rightSubsum;
    }

    public int helper(int[] nums, int left, int right) {
        if (left == right) return nums[left];

        int p = (left + right) / 2;

        int leftSum = helper(nums, left, p);
        int rightSum = helper(nums, p + 1, right);
        int crossSum = crossSum(nums, left, right, p);

        return Math.max(Math.max(leftSum, rightSum), crossSum);
    }

    public int maxSubArray(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }

    public static int[] deleteDumplicate1(int[] a, int val) {

        int i = 0;
        for (int j = 0; j < a.length; j++) {
            if (a[j] != val) {
                a[i] = a[j];
                i++;
            }

        }
        return a;
    }

    public static int[] deleteDumplicate2(int[] a, int val) {

        int i = 0;
        int n = a.length;
        while (i < n) {
            if (a[i] == val) {
                a[i] = a[n - 1];
                n--;
            } else {
                i++;
            }
        }
        return a;
    }

    /**
     * 对于一个有序数组,查找指定值所在的位置
     * 如果不存在,则返回其插入的位置.
     *
     * @param a
     * @param val
     * @return
     */
    public static int getPosition(int[] a, int val) {

        int lo = 0;
        int high = a.length - 1;
        while (lo <= high) {
            int middle = lo + (high - lo) / 2;
            if (a[middle] == val) {
                return middle;
            } else if (a[middle] < val) {
                lo = middle + 1;
            } else if (a[middle] > val) {
                high = middle - 1;
            }
        }
        return lo;

    }

    /**
     * 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
     * <p>
     * 说明：本题中，我们将空字符串定义为有效的回文串。
     * <p>
     * 示例 1:
     * <p>
     * 输入: "A man, a plan, a canal: Panama"
     * 输出: true
     * 示例 2:
     * <p>
     * 输入: "race a car"
     * 输出: false
     * <p>
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/xah8k6/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     *
     * @param s
     * @return
     */
    public boolean isPalindrome(String s) {
        if (s == null) {
            return false;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isLetterOrDigit(c)) {
                sb.append(c);
            }
        }
        return isPalindromeHelper(sb.toString().toLowerCase());
    }

    private boolean isPalindromeHelper(String s) {
        int lo = 0;
        int hi = s.length() - 1;
        while (lo <= hi) {
            if (s.charAt(lo) != s.charAt(hi)) {
                return false;
            }
            lo++;
            hi--;
        }
        return true;
    }

    /**
     * 原地双指针法
     *
     * @return
     */
    public boolean isPalindrome2(String s) {
        int n = s.length();
        int lo = 0;
        int hi = n - 1;
        while (lo < hi) {
            while (lo < hi && !Character.isLetterOrDigit(s.charAt(lo))) {
                lo++;
            }
            while (lo < hi && !Character.isLetterOrDigit(s.charAt(hi))) {
                hi--;
            }
            if (lo < hi) {
                if (Character.toLowerCase(s.charAt(lo)) != Character.toLowerCase(s.charAt(hi))) {
                    return false;
                }
                lo++;
                hi--;
            }
        }
        return true;
    }

    /**
     * 分割回文串
     *
     * @param s
     * @return
     */
    public List<List<String>> partition(String s) {
        int len = s.length();
        List<List<String>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        // Stack 这个类 Java 的文档里推荐写成 Deque<Integer> stack = new ArrayDeque<Integer>();
        // 注意：只使用 stack 相关的接口
        Deque<String> stack = new ArrayDeque<>();
        backtracking(s, 0, len, stack, res);
        return res;
    }

    /**
     * @param s
     * @param start 起始字符的索引
     * @param len   字符串 s 的长度，可以设置为全局变量
     * @param path  记录从根结点到叶子结点的路径
     * @param res   记录所有的结果
     */
    private void backtracking(String s, int start, int len, Deque<String> path, List<List<String>> res) {
        //递归,回溯结束的条件
        if (start == len) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < len; i++) {

            // 因为截取字符串是消耗性能的，因此，采用传子串索引的方式判断一个子串是否是回文子串
            // 不是的话，剪枝
            if (!checkPalindrome(s, start, i)) {
                continue;
            }
            //path添加截取的字符
            path.addLast(s.substring(start, i + 1));
            backtracking(s, i + 1, len, path, res);
            path.removeLast();
        }
    }

    /**
     * 这一步的时间复杂度是 O(N)，因此，可以采用动态规划先把回文子串的结果记录在一个表格里
     *
     * @param str
     * @param left  子串的左边界，可以取到
     * @param right 子串的右边界，可以取到
     * @return
     */
    private boolean checkPalindrome(String str, int left, int right) {
        // 严格小于即可
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    /**
     * leet
     * [le,et]
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> hashSet = new HashSet<>(wordDict);
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 1; i < n + 1; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && hashSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }

}
